package problem210_Course_Schedule_II;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;

public class Solution {
	 public int[] findOrder(int numCourses, int[][] prerequisites) {
		 int[] inDegree=new int[numCourses];
		 Map<Integer,List<Integer>> graph=new HashMap<>();
		 for(int[] s:prerequisites){
			 inDegree[s[0]]++;
			 if(graph.containsKey(s[1])){
				 graph.get(s[1]).add(s[0]);
			 }else{
				 graph.put(s[1], new LinkedList<>());
				 graph.get(s[1]).add(s[0]);
			 }
		 }
		 Queue<Integer> queue=new LinkedList<>();
		 int count=0;int[] result=new int[numCourses];
		 for(int i=0;i<inDegree.length;i++){
			 if(inDegree[i]==0)
				 queue.add(i);
		 }
		 while(!queue.isEmpty()){
			 int top=queue.poll();
			 result[count++]=top;
			 List<Integer> adj=graph.get(top);
			 if(adj!=null){
				 for(int j:adj){
					 inDegree[j]--;
					 if(inDegree[j]==0)
						 queue.add(j);
				 }
			 }
		 }
		 return count==numCourses?result:new int[0];
	 }
}
